package tests;

import java.util.ArrayList;
import java.util.List;

public class Keyongyu {
    public static void main(String[] args) {
        //把一对兔子看成一个整体
        int N = 12;
        System.out.println("count1=" + (2 * getRabbitCount(N)));
        System.out.println("count2=" + (2 * getRabbitCount2(N)));
    }

    /**
     * @param num 月数
     * @return 多少对兔子
     */
    public static int getRabbitCount2(int num) {
        if(num == 1 || num == 2) {
            return 1;
        }else {
            //指定月的兔子数=前面2个月的兔子数相加
            return getRabbitCount2(num - 2) + getRabbitCount2(num - 1);
        }
    }

    public static int getRabbitCount(int N){
        //刚开始的第一对兔子
        Rabbit rabbit = new Rabbit(Rabbit.sIndex++);
        int count = 1;
        for (int i = 1; i <= N; i++) {
            count += addMouths(rabbit);
        }
        return count;
    }

    private static int addMouths(Rabbit rabbit) {
        int count = 0;
        rabbit.mouths++;
        if (rabbit.canMakeChild()) {
            //是否可以生兔子
            count++;
            Rabbit c = new Rabbit(Rabbit.sIndex++);
            rabbit.childes.add(c);
            System.out.println(rabbit.index + " 生了 " + c.index);
        }
        for (Rabbit c : rabbit.childes) {//遍历兔子的直系后代
            count += addMouths(c);
        }
        return count;
    }

    public static class Rabbit {
        public int index;
        public static int sIndex = 1;

        public Rabbit(int index) {
            this.index = index;
        }

        public int mouths;

        //直系二代兔子
        public List<Rabbit> childes = new ArrayList<>();

        public boolean canMakeChild() {
            return mouths > 2;
        }
    }
}